package xiaomin.demo.algorithm;

import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;
/*
给定 一个 没有 重叠 的 区间 序列， 现 插入 一个 新的 区间 到 该 序列 中， 要求 维持 没有 重叠 的 情况。
假设 该 序列 存放 的 区间 是 有序 的。 区间 定义 如 题目“ 重叠 区间 个数”。

陈东锋. 进军硅谷:程序员面试揭秘 (技术移民参考手册) (p. 69). 电子工业出版社. Kindle 版本.

思路：
1.构造新的区间列表 newInterList
2.遍历区间列表intervals,如果区间在新插入的区间左边，复制到 newInterList
3.碰到重叠的区间,合并区间,然后复制到newInterList
4.比新区间更大的区间,复制到newInterList
 */
public class Lesson07 {
    static class Interval{
        int start;
        int end;
        Interval(int a,int b){
            start=a;
            end=b;
        }

        @Override
        public String toString() {
            return "Interval{" +
                    "start=" + start +
                    ", end=" + end +
                    '}';
        }
    }



    public static void run() {
        //构建4个区间
        Interval[] intervals = new Interval[4];
        intervals[0] = new Interval(2, 5);
        intervals[1] = new Interval(6, 10);
        intervals[2] = new Interval(11, 20);
        intervals[3] = new Interval(30, 40);
        //新插入的区间
        Interval newInteral=new Interval(1,10);

        List<Interval> newInterList=new ArrayList<Interval>();
        int mergedStart=newInteral.start;
        int mergedEnd=newInteral.end;
        int insertFlag=0;
        int i=0,n=intervals.length;

        //区间不重叠，且在插入区间左边
        while(i<n && intervals[i].end<newInteral.start){
            newInterList.add(intervals[i]);
            i++;
        }
        //区间重叠,合并区间
        while (i<n && intervals[i].start<newInteral.end){
            mergedStart=Math.min(mergedStart,newInteral.start);//合并区间最小值
            mergedEnd=Math.max(mergedEnd,newInteral.end);
            i++;
        }
        //插入区间
        newInterList.add(new Interval(mergedStart,mergedEnd));

        //区间不重叠,且在插入区间右边
        while (i<n && newInteral.end<intervals[i].start){
            newInterList.add(intervals[i]);
            i++;
        }

//        for(Interval interval:intervals){
//            //区间不重叠,并且比插入区间小
//            if(interval.end<newInteral.start){
//                newInterList.add(interval);
//            }//区间不重叠，并且比插入区间大
//            else if(newInteral.end<interval.start){
//                newInterList.add(interval);
//            }
//            else {//区间重叠，合并
//                mergedStart=Math.min(mergedStart,interval.start);//合并区间最小值
//                mergedEnd=Math.max(mergedEnd,interval.end);
//                if(insertFlag==0) {
//                    newInterList.add(new Interval(mergedStart,mergedEnd));
//                    insertFlag=1;
//                }
//                else{
//                    newInterList.get(newInterList.size()-1).start=mergedStart;
//                    newInterList.get(newInterList.size()-1).end=mergedEnd;
//                }
//            }
//        }


        //声明点列表
//        List<Point> pointList=new ArrayList<Point>();
//        for(Interval interval:intervals){
//            pointList.add(new Point(interval.start,0));
//            pointList.add(new Point(interval.end,1));
//        }


        //插入新区间的两个点
//        pointList.add(new Point(newInteral.start,0));
//        pointList.add(new Point(newInteral.end,1));
//
//        //对点排序
//        Collections.sort(pointList);
//
//        int openCount=0;

//        for(Point p:pointList){
//            if(p.type==0){//区间打开
//                if(openCount==0){//新的区间
//                    newInterList.add(new Interval(p.value,0));
//                }
//                openCount++;
//            }
//            else {//区间关闭
//                if(openCount==1) {//区间结束
//                    newInterList.get(newInterList.size() - 1).end = p.value;
//                }
//                openCount--;
//            }
//        }

        //输出新的区间
        for(Interval interval: newInterList){
            System.out.println(interval.toString());
        }
    }
}
